10003 - Cutting sticks/robado.cpp

   1 //http://acm.uva.es/board/viewtopic.php?t=1543&highlight=10003&sid=707852836d9f5e46db0ea0865323a05f
   2
   3 #include<stdio.h>
   4 #include<values.h>
   5
   6 #define MAX 60
   7 #define inf MAXLONG
   8
   9 int main()
  10 {
  11  long L,N,i,j,n,x,y,q,l,k,t,sum,m[MAX][MAX],p[MAX];
  12
  13  while(scanf("%ld",&L)==1 && L)
  14  {
  15    scanf("%ld",&N);
  16
  17    y = 0;
  18
  19    for(i=1;i<=N;i++)
  20        {
  21    scanf("%ld",&x);
  22    p[i] = x - y;
  23    y = x;
  24        }
  25    p[i] = L - y;
  26
  27    n = i;
  28
  29    for(i=0;i<=n;i++)
  30        m[i][i] = 0;
  31
  32    for(l=2;l<=n;l++)
  33       {
  34    for(i=1;i<=n-l+1;i++)
  35       {
  36        j = i + l - 1;
  37        m[i][j] = inf;
  38
  39
  40        for(k=i;k<=j-1;k++)
  41           {
  42       q = m[i][k] + m[k+1][j] ;
  43
  44       sum = 0;
  45
  46       for(t=i;t<=j;t++)
  47           sum += p[t];
  48
  49       q += sum;
  50
  51       if(q<m[i][j])
  52          m[i][j] = q;
  53           }
  54       }
  55       }
  56
  57     printf("The minimum cutting is %ld.\n",m[1][n]);
  58  }
  59  return 0;
  60 }